#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
//冒泡
void bubble_sort(vector<int>& str, int len) {
	for (int i = 0; i < len - 1; i++) {
		for (int j = 1; j < len - i; j++) {
			if (str[j] < str[j - 1]) {
				//change
				int val = str[j];
				str[j] = str[j - 1];
				str[j - 1] = val;
			}
		}
	}
}
//插入
void insert_sort(vector<int>& str, int len) {
	for (int i = 1; i < len; i++) {
		for (int j = i; j > 0&&str[j]<str[j-1]; j--) {
			::swap(str[j], str[j - 1]);
		}
	}
}
//选择
void select_sort(vector<int>& str, int len) {
	int key;
	for (int i = 0; i < len; i++) {
		key = i;
		for (int j = i + 1; j < len; j++) {
			if (str[key] > str[j]) key = j;
		}
		int val = str[i];
		str[i] = str[key];
		str[key] = val;
	}
}
//快排
int  quick_sortval (vector<int>& str,int poll,int right){
	int point = str[poll];
	while (poll < right) {
		while (poll < right && str[right] >= point) right--;
		str[poll] = str[right];
		while (poll < right && str[poll] <= point) poll++;
		str[right] = str[poll];
	}
	str[poll] = point;
	return poll;
}
void quick_sort(vector<int>& str ,int left ,int right) {
	if (left < right) {
		int pos = quick_sortval(str, left, right);
		quick_sort(str, left, pos - 1);
		quick_sort(str, pos + 1, right);
	}
}

//希尔
void shell_sort(vector<int>& str, int len) {
	int d,i,j;
	for (d = len / 2; d >= 1; d /= 2) {
		for (i = d; i < len; i++) {
			if (str[i] < str[i - d]) {
				for (j = i; j >=d&&str[j-d]>str[j]; j = j - d) {
					::swap(str[j], str[j - d]);
				}
			}
		}
	}
}

//堆排序
void headadjust(vector<int>& str, int len,int i) {
	int j;
	for (j = i * 2 + 1; j < len; j = j * 2+1) {
		if (j < len-1 && str[j] < str[j + 1]) {
			j++;
		}
		if (str[i] < str[j]) {
			::swap(str[i], str[j]);
			i = j;
		}
		else {
			break;
		}
	}
}
void heap_sort(vector<int>& str, int len) {
	int i;
	for (i = (len / 2)-1; i > 0; i--) {
		//first sort get max_val
		headadjust(str, len, i);
	}
	for (i = len - 1; i > 0; i--) {
		::swap(str[0], str[i]);
		headadjust(str, i, 0);
	}
}

//归并排序
void merge_judge(vector<int>& str, int left, int right, int mid) {
	int i, j, p;
	vector<int> temp(str.size());
	i = left;
	j = mid;
	p = left;
	while (i < mid && j <= right) {
		if (str[i] < str[j])   temp[p++] = str[i++];
		else    temp[p++] = str[j++];

	}
	while (i < mid) {
		temp[p++] = str[i++];
	}
	while (j <= right) {
		temp[p++] = str[j++];
	}
	//将temp赋值给str
	p = left;
	i = left;
	while (i <= right) {
		str[i++] = temp[p++];
	}
}

void merge_sort(vector<int>& str, int left, int right) {
	if (left < right) {
		int mid = (left + right) / 2;
		merge_sort(str, left, mid);
		merge_sort(str, mid + 1, right);
		merge_judge(str, left, right, mid + 1);
	}
}


int main() {
	vector<int> str= { 211,1,5,-1,-57,34,-97,102,13,12 };
	int len = str.size();
	//bubble_sort(str,len);
	
	//insert_sort(str,len);
	
	//select_sort(str, len);

	//quick_sort(str,0,str.size()-1);

	//shell_sort(str, len);

	//merge_sort(str, 0, len - 1);

	//heap_sort(str, len);
	for (auto k : str) {
		cout << k<<"  ";
	}
	cout << endl;
}

